package com.example.lcode.binary;

public class Question300 {

    public int lengthOfLIS(int[] nums) {
        // 记录的是 长度为 i 的最后一个值
        int []record = new int[nums.length + 1];
        record[1] = nums[0];
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > record[len]) {
                // 处理长度增量值
                len ++;
                record[len] = nums[i];
            } else {
                // 修复存量数据
                int index = findIndex(record, 1, len,  nums[i]);
                record[index] = nums[i];
            }
        }
        return len;
    }

    private int findIndex(int[] record, int left, int right, int target) {
        if (left > right) {
            return 1;
        }
        int mid = (left + right) / 2;
        if (target > record[mid] && target < record[mid + 1]) {
            return mid + 1;
        } else if (target > record[mid + 1]) {
            return findIndex(record, mid + 1, right, target);
        } else {
            return findIndex(record, left, mid - 1, target);
        }
    }

    public static void main(String[] args) {
        Question300 question300 = new Question300();
        int []arr = {3,5,6,2,5,4,19,5,6,7,12};
        int i = question300.lengthOfLIS(arr);
        System.out.println(i);
    }

}
